Лемма о существовании простой цепи

Если вершины $v$ и $w$ связаны в графе, то между ними есть простая цепь.

Поскольку вершины $v$ и $w$ связаны, между ними существует цепь. Возьмем кратчайшую из таких цепей: $$v = v_0, v_1, v_2, \ldots, v_k = w$$ Предположим, что эта цепь не является простой. Тогда в ней есть повторяющиеся вершины, то есть $\exists{i < j}\mathpunct{:}~~ v_i = v_j$. В этом случае мы можем удалить из цепи участок от $v_i$ до $v_j$ и получить новую, более короткую цепь: $$v = v_0, \ldots, v_i, v_{j+1}, \ldots, v_k = w$$ Это противоречит нашему выбору кратчайшей цепи. Следовательно, кратчайшая цепь между любыми двумя связанными вершинами всегда является простой. $\square$